Game Physics Pearls by Gino van Den Bergen & Dirk Gregorius

Author:Gino van Den Bergen & Dirk Gregorius
Language: eng
Format: mobi, epub
Tags: Games, Computers, Programming, Video & Animation, Digital Media
ISBN: 9781568814742
Publisher: Taylor & Francis
Published: 2010-07-23T00:00:00+00:00

i

i

i

i

160

7. Parallelizing Particle-Based Simulation on Multiple Processors

Note that this does not include the ghost particles of p 1 from p 1. From Equa-

tions (7.1) and (7.2), the particles that have to be sent to p 1 are

SP t+Δ t

=

EP t+Δ t + GP t+Δ t

0 → 1

0 → 1

0 → 1

=

{i|xt+Δ t > m − g, xt ≤ m},

i

i

as shown in Figure 7.3.

To send the data, SP t+Δ t has to be selected from all the particles in the mem-

0 → 1

ory of a processor. Flagging particles in the region and using prefix sums, which

is often used in algorithms on the GPU [Harris et al. 07] to compact them to a

dense memory, adds some computation cost which may seem negligible, but not

for high-frequency applications like our problem. Most of the processors have

to select two sets of particles on each sides for two neighbors if more than two

processors are used. This means we have to run these kernels twice.

Instead, the grid constructed for efficient neighbor search is reused to select

the particles in our implementation. The data can be directly used to select the

particles so that we can avoid increasing the cost. The particles that have to be sent

to C 0 are particles in voxels with xv > m − g. However, the grid constructed in

this simulation step cannot be used directly because particles have changed their

positions in the time step. To avoid the full build of the grid, we used a simulation

condition to restrict the particles we want to find. We used the distinct element

method (DEM) to calculate force on a particle by placing springs and dampers.

DEM is an explicit method but is not unconditionally stable. It has to restrict the

size of the time step according to the velocity to maintain stability. Thus, we need

vΔ t/l 0 < c, where v, Δ t, l 0 , and c are particle velocity, time-step size, particle diameter, and Caulant number, respectively, which have to be less than one. This

condition guarantees that the motion of any particle is below its diameter. Since

we set the side length of a voxel equal to the particle diameter, particles do not

move more than l 0, which is the side length of a voxel. From these conditions,

we find SP t+Δ t in simulation time t are the particles (let the x-coordinate of this 0 → 1

be x) in

S

= {m − d − l

0 → 1

0 < x ≤ m},

and especially when d = re,

S

= {m − 2 d < x ≤ m}.

0 → 1

A buffer has to be prepared to store these selected particles. When a uniform

grid is used and g = re, two voxel widths in the direction of the space split have

to be sent. The buffer size can be calculated from the configuration of the grid.

i

i

i

i

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.